package m202405.d12;

import java.util.Map;
import java.util.PriorityQueue;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/5/12 10:51
 */
public class Q239 {

    public static void main(String[] args) {
        Q239 q239 = new Q239();
        q239.maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3);
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        PriorityQueue<int[]> queue = new PriorityQueue<>((a1, a2) -> a1[0] == a2[0] ? a2[1] - a1[1] : a2[0] - a1[0]);
        int[] max = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length - k + 1; i++) {
            if (queue.isEmpty()) {
                for (int j = 0; j < k; j++) {
                    queue.add(new int[]{nums[j], j});
                }
            } else {
                queue.add(new int[]{nums[i + k - 1], i + k - 1});
            }
            while (queue.peek()[1] < i) {
                queue.poll();
            }
            max[i] = queue.peek()[0];
        }
        return max;
    }

//    public int[] maxSlidingWindow(int[] nums, int k) {
//        PriorityQueue<Integer> queue = new PriorityQueue<>((i1, i2) -> i2 - i1);
//        int[] max = new int[nums.length - k + 1];
//        for (int i = 0; i < nums.length - k + 1; i++) {
//            if (queue.isEmpty()) {
//                for (int j = 0; j < k; j++) {
//                    queue.add(nums[j]);
//                }
//            } else {
//                queue.remove(nums[i - 1]);
//                queue.add(nums[i + k - 1]);
//            }
//            max[i] = queue.peek();
//        }
//        return max;
//    }

//    private int max(int[] nums, int start, int end, int lastMax) {
//        if (lastMax != Integer.MIN_VALUE) {
//            if (nums[start - 1] < lastMax && nums[end] <= lastMax) {
//                return lastMax;
//            }
//        }
//        int max = Integer.MIN_VALUE;
//        for (int i = start; i <= end; i++) {
//            max = Math.max(max, nums[i]);
//        }
//        return max;
//    }
}
